Link to this headingHVZK (Square Free)

This proof is used to show that a number does not contain a square.

Link to this headingInteractive protocol

Implementation:

from Crypto.PublicKey import RSA from Crypto.Util.number import inverse, getRandomInteger, getStrongPrime, isPrime from math import gcd def prime_product_constant(max_const=65537): print("Calculating Prime Const") i = 5 ret = 1*2*3 while i < max_const: if isPrime(i): ret *= i i+=2 return ret def verifier_part1(size, num_challenges): #Randomly generate challenges return [getRandomInteger(size//2) for _ in range(num_challenges)] def prover_part2(size, challenges): #Generate Key print("Generating Key") mykey = RSA.generate(size) private_p, private_q, public_n, private_phi = [mykey.p, mykey.q, mykey.n, (mykey.p - 1) * (mykey.q - 1)] #Calculate the inverse for the power m = inverse(public_n, private_phi) #Calculate Proofs # challenge ^ m % N return [public_n, [pow(chal, m, public_n) for chal in challenges]] def verifier_part3(challenges, proofs, public_n, alpha_const=319567): #Check Varables assert public_n > 1 #Check that N is not devisible by primes smaller than 65537, or 319567 prime_product = prime_product_constant(alpha_const) assert gcd(prime_product, public_n) == 1 #Check that proof is greater than 0 for proof in proofs: assert (proof % public_n) > 0 #Validate Challenges for idx in range(num_challenges): #Compute test tmp = pow(proofs[idx], public_n, public_n) #Check that chal^m = proof^N #print(f"Testing Proof {challenges[idx]}, {tmp}") assert tmp == challenges[idx] return True if __name__ == '__main__': #Setup num_challenges = 5 size = 1024 #Get challenges from Verifier challenges = verifier_part1(size, num_challenges) #Generate Profs from the challenges public_n, proofs = prover_part2(size, challenges) #From the proofs verify that they are correct valid = verifier_part3(challenges, proofs, public_n) print(f"Challenges have been confirmed: {valid}")

Link to this headingNon-Interactive Protocol

The main part of this protocol is using a common random number generator so that it is unique and static for each side

Implementation:

from Crypto.PublicKey import RSA from Crypto.Util.number import inverse, getRandomInteger, getStrongPrime, isPrime from math import gcd import hashlib def prime_product_constant(max_const=65537): print("Calculating Prime Const") i = 5 ret = 1*2*3 while i <= max_const: if isPrime(i): ret *= i i+=2 return ret def generate_challenges(size, public_n, num_challenges, salt="squarefreeproof", hash_obj=hashlib.shake_256): counter = 0 outputs = [] #print(f"size: {size}, public_n: {public_n}, num_challenges: {num_challenges}") while len(outputs) < num_challenges: #Generate Order of inputs hash_list = [str(public_n), str(num_challenges), salt, str(counter)] #Generate String to hash with sizes hash_list = [str(len(s)) + s for s in hash_list] #Join to gether with "|" str_input = "|" + "|".join(hash_list) hash_output = hash_obj(str_input.encode("utf8")).digest(size//8) #print(f"hash_in:{str_input.encode("utf8")}, hash_out:{hash_output}") hash_int = (int.from_bytes(hash_output, byteorder='little') % public_n) #Check that gcd(hash_int,N)=1 if gcd(hash_int, public_n) == 1: outputs.append(hash_int) counter += 1 return outputs def prover_part1(size, num_challenges): #Generate Key print("Generating Key") mykey = RSA.generate(size) private_p, private_q, public_n, private_phi = [mykey.p, mykey.q, mykey.n, (mykey.p - 1) * (mykey.q - 1)] #Randomly generate challenges challenges = generate_challenges(size, public_n, num_challenges) #print(f"Challenges: {challenges}") #Calculate the inverse for the power m = inverse(public_n, private_phi) #Calculate Proofs # challenge ^ m % N proofs = [pow(chal, m, public_n) for chal in challenges] #print(f"Proofs: {proofs}") return [public_n, proofs] def verifier_part2(size, public_n, proofs, alpha_const=319567): #Check Varables assert public_n > 1 #Check that N is not divisible by primes smaller than 65537, or 319567 prime_product = prime_product_constant(alpha_const) assert gcd(prime_product, public_n) == 1 #Check that proof is greater than 0 for proof in proofs: assert (proof % public_n) > 0 #Generate Challenges challenges = generate_challenges(size, public_n, len(proofs)) #print(f"Challenges: {challenges}") #Validate Challenges for idx in range(len(challenges)): #Compute test tmp = pow(proofs[idx], public_n, public_n) #Challenge = proof^n #print(f"Testing Proof {challenges[idx]}, {tmp}") assert tmp == challenges[idx] return True if __name__ == '__main__': #Setup num_challenges = 5 size = 1024 #Get challenges from Verifier public_n, proofs = prover_part1(size, num_challenges) #Generate Profs from the challenges valid = verifier_part2(size, public_n, proofs) print(f"Challenges have been confirmed: {valid}")

Link to this headingSecurity

Input validation: Insure checks for valid transmitted values
Implicit Trust of Prover:
- Ensure generator_g and mod_q are valid known values
- recalculate and check the random_c from the hashed values
Missing Values:
- if shared_h or shared_u are missing its a major issue
- if generator_g or mod_q are missing it might be an issue
Weak Randomness:
- If there are two separate verifications with the same secret_r with different data this can leak the secret_x. https://www.zkdocs.com/docs/zkdocs/zero-knowledge-protocols/schnorr/
Replay Attacks: Ensure there is a ID to both the verifier and prover to prevent replay attacks

Link to this headingMalicious Versifiers (Interactive)

If the versifier sends non random values to the prover it is possible to factor N by learning of phi(N).

Link to this headingMalicious Prover with non uniform values (Interactive/Non-Interactive)

The Prover can choose random proof values and then generate the correct challenge variables. This only works if the generation is not random

challenge = pow(fake_proof, public_n, public_n)

Link to this headingMalicious Prover (Non-Interactive)

  1. Dont trust the challenge values provided by the prover. Generate them yourself.
    • You could just sent challenge = 1 and proof = 1
  2. If the proof is not validated mod N then you can use proof + kN for replaying
  3. Not trusting the size of the verifications from the prover